/**
  @(#)$Id: AL_QueueList.h 74 2013-10-10 12:42:07Z xiaoting $
  @brief   A queue is a special linear form, so special is that it only allows the front end of the table (front) delete operation, 
  and the rear end of the table (rear) for insertion, and the stack, as the queue is an operating by restricted linear form. Insert 
  operation is called the tail end, the end delete operation called HOL. No element in the queue, it is called an empty queue.
  
  This data structure in the queue, the first element inserted will be the first element to be removed; otherwise the last inserted 
  element will be the last element to be removed, so the queue is also known as "first in first out" (FIFO-first in first out) linear 
  form.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:42:07 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 74 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueList.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueList.h 74 2013-10-10 12:42:07Z xiaoting $
 */

#ifndef CXX_AL_QUEUELIST_H
#define CXX_AL_QUEUELIST_H

#ifndef CXX_AL_NODE_H
#include "AL_Node.h"
#endif

///////////////////////////////////////////////////////////////////////////
//			AL_QueueList
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_QueueList
{
public:
	/**
	* Construction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	AL_QueueList();

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_QueueList();

	/**
	* IsEmpty
	*
	* @param	VOID
	* @return	BOOL
	* @note		Returns true queue is empty
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Front
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the first element at the front of the queue.
	* @attention
	*/
	BOOL Front(T& tTypeOut) const;

	/**
	* Back
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Returns a reference to the last and most recently added element at the back of the queue.
	* @attention
	*/
	BOOL Back(T& tTypeOut) const;

	/**
	* Pop
	*
	* @param	T& tTypeOut <OUT>
	* @return	BOOL
	* @note		Removes an element from the front of the queue.
	* @attention
	*/
	BOOL Pop(T& tTypeOut);

		
	/**
	* Push
	*
	* @param	const T& tData
	* @return	BOOL
	* @note		Adds an element to the back of the queue.
	* @attention	
	*/
	BOOL Push(const T& tData);

	/**
	* Size
	*
	* @param	VOID
	* @return	DWORD
	* @note		Returns the number of elements in the queue
	* @attention
	*/
	DWORD Size() const;

	/**
	* Clear
	*
	* @param	VOID
	* @return	VOID
	* @note		clear all data
	* @attention
	*/
	VOID Clear();
	
protected:
private:
	/**
	*Copy Construct
	*
	* @param const AL_QueueList<T>& cAL_QueueList
	* @return
	*/
	AL_QueueList(const AL_QueueList<T>& cAL_QueueList);

	/**
	*Assignment
	*
	* @param const AL_QueueList<T>& cAL_QueueList
	* @return AL_QueueList<T>&
	*/
	AL_QueueList<T>& operator = (const AL_QueueList<T>& cAL_QueueList);

public:
protected:
private: 
	AL_Node<T>*		m_pHeader;
	DWORD			m_dwSize;

	AL_Node<T>*		m_pFront;
	AL_Node<T>*		m_pRear;
};


/**
* Construction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_QueueList<T>::AL_QueueList():
m_pHeader(NULL),
m_dwSize(0x00),
m_pFront(NULL),
m_pRear(NULL)
{
	m_pHeader = new AL_Node<T>;
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_QueueList<T>::~AL_QueueList()
{
	Clear();
	//delete the header
	if (NULL != m_pHeader) {
		delete m_pHeader;
		m_pHeader = NULL;
	}
}

/**
* IsEmpty
*
* @param	VOID
* @return	BOOL
* @note		Returns true queue is empty
* @attention
*/
template<typename T> BOOL 
AL_QueueList<T>::IsEmpty() const
{
	return (0x00 == m_pHeader->m_pNext) ? TRUE:FALSE;
}


/**
* Front
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the first element at the front of the queue.
* @attention
*/
template<typename T> BOOL 
AL_QueueList<T>::Front(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pFront->m_tData;
	return TRUE;
}

/**
* Back
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Returns a reference to the last and most recently added element at the back of the queue.
* @attention
*/
template<typename T> BOOL 
AL_QueueList<T>::Back(T& tTypeOut) const
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}

	tTypeOut = m_pRear->m_tData;
	return TRUE;
}

/**
* Pop
*
* @param	T& tTypeOut <OUT>
* @return	BOOL
* @note		Removes an element from the front of the queue.
* @attention
*/
template<typename T> BOOL 
AL_QueueList<T>::Pop(T& tTypeOut)
{
	if (TRUE ==IsEmpty()) {
		return FALSE;
	}
	
	AL_Node<T>*	pPop = m_pFront;
	//get the previous node of m_pRear
	m_pHeader->m_pNext = m_pFront->m_pNext;
	m_pFront = m_pHeader->m_pNext;
	tTypeOut = pPop->m_tData;

	//delete the top
	delete pPop;
	pPop = NULL;

	m_dwSize--;
	return TRUE;
}

	
/**
* Push
*
* @param	const T& tData
* @return	BOOL
* @note		Adds an element to the back of the queue.
* @attention	
*/
template<typename T> BOOL 
AL_QueueList<T>::Push(const T& tData)
{
	AL_Node<T>*	pPush = new AL_Node<T>;
	if (NULL == pPush) {
		//new error
		return FALSE;
	}
	pPush->m_tData = tData;

	if (TRUE == IsEmpty()) {
		//the first time Push, not need to ++
		m_pHeader->m_pNext = pPush;
		m_pFront = m_pHeader->m_pNext;
		m_pRear = pPush;
	}
	else {
		m_pRear->m_pNext = pPush;
		m_pRear = pPush;
	}

	m_dwSize++;
	return TRUE;
}

/**
* Size
*
* @param	VOID
* @return	DWORD
* @note		Returns the number of elements in the queue
* @attention
*/
template<typename T> DWORD 
AL_QueueList<T>::Size() const
{
	return m_dwSize;
}

/**
* Clear
*
* @param	VOID
* @return	VOID
* @note		clear all data
* @attention
*/
template<typename T> VOID 
AL_QueueList<T>::Clear()
{
	AL_Node<T>* pDelete = NULL;
	while(NULL != m_pHeader->m_pNext){
		//get the node
		pDelete = m_pHeader->m_pNext;
		m_pHeader->m_pNext = pDelete->m_pNext;
		delete pDelete;
		pDelete = NULL;
	}
	m_dwSize = 0x00;
}

#endif // CXX_AL_QUEUELIST_H
/* EOF */
